UnivTrevesV1, Main, Exploration, bibRecord, 000867

An Exact Exponential Time Algorithm for POWER DOMINATING SET

Identifieur interne : 000867 ( Main/Exploration ); précédent : 000866; suivant : 000868

An Exact Exponential Time Algorithm for POWER DOMINATING SET

Auteurs : Daniel Binkele-Raible [Allemagne] ; Henning Fernau [Allemagne]

Source :

Algorithmica [ 0178-4617 ] ; 2012.

RBID : Pascal:12-0145043

Descripteurs français

Pascal (Inist)
- Arbre recherche, Théorie non locale, Pointeur, Ensemble dominant, Théorie graphe, Problème NP difficile, Graphe cubique, Résolution problème, Sous graphe, Algorithmique, ..

English descriptors

KwdEn :
- Algorithmics, Cubic graph, Dominating set, Graph theory, NP hard problem, Non local theory, Pointer, Problem solving, Search tree, Subgraph.

Abstract

The POWER DOMINATING SET problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: given a graph G(V, E), a set P ⊆ V is a power dominating set if every vertex is observed after the exhaustive application of the following two rules. First, a vertex is observed if v ∈ P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed, as well. We show that POWER DOMINATING SET remains NP-hard on cubic graphs. We design an algorithm solving this problem in time O^*(1.7548ⁿ) on general graphs, using polynomial space only. To achieve this, we introduce so-called reference search trees that can be seen as a compact representation of usual search trees, providing non-local pointers in order to indicate pruned subtrees.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000310
to stream PascalFrancis, to step Curation: 000A19
to stream PascalFrancis, to step Checkpoint: 000223
to stream Main, to step Merge: 000891
to stream Main, to step Curation: 000867

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">An Exact Exponential Time Algorithm for POWER DOMINATING SET</title>
<author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik/Wirtschaftsinformatik, Universitat Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>Trier</wicri:noRegion>
<wicri:noRegion>Universitat Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik/Wirtschaftsinformatik, Universitat Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>Trier</wicri:noRegion>
<wicri:noRegion>Universitat Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">12-0145043</idno>
<date when="2012">2012</date>
<idno type="stanalyst">PASCAL 12-0145043 INIST</idno>
<idno type="RBID">Pascal:12-0145043</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000310</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000A19</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000223</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000223</idno>
<idno type="wicri:doubleKey">0178-4617:2012:Binkele Raible D:an:exact:exponential</idno>
<idno type="wicri:Area/Main/Merge">000891</idno>
<idno type="wicri:Area/Main/Curation">000867</idno>
<idno type="wicri:Area/Main/Exploration">000867</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">An Exact Exponential Time Algorithm for POWER DOMINATING SET</title>
<author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik/Wirtschaftsinformatik, Universitat Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>Trier</wicri:noRegion>
<wicri:noRegion>Universitat Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik/Wirtschaftsinformatik, Universitat Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>Trier</wicri:noRegion>
<wicri:noRegion>Universitat Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Algorithmica</title>
<title level="j" type="abbreviated">Algorithmica</title>
<idno type="ISSN">0178-4617</idno>
<imprint><date when="2012">2012</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Algorithmica</title>
<title level="j" type="abbreviated">Algorithmica</title>
<idno type="ISSN">0178-4617</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithmics</term>
<term>Cubic graph</term>
<term>Dominating set</term>
<term>Graph theory</term>
<term>NP hard problem</term>
<term>Non local theory</term>
<term>Pointer</term>
<term>Problem solving</term>
<term>Search tree</term>
<term>Subgraph</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Arbre recherche</term>
<term>Théorie non locale</term>
<term>Pointeur</term>
<term>Ensemble dominant</term>
<term>Théorie graphe</term>
<term>Problème NP difficile</term>
<term>Graphe cubique</term>
<term>Résolution problème</term>
<term>Sous graphe</term>
<term>Algorithmique</term>
<term>.</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The POWER DOMINATING SET problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: given a graph G(V, E), a set P ⊆ V is a power dominating set if every vertex is observed after the exhaustive application of the following two rules. First, a vertex is observed if v ∈ P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed, as well. We show that POWER DOMINATING SET remains NP-hard on cubic graphs. We design an algorithm solving this problem in time O<sup>*</sup>
(1.7548<sup>n</sup>
) on general graphs, using polynomial space only. To achieve this, we introduce so-called reference search trees that can be seen as a compact representation of usual search trees, providing non-local pointers in order to indicate pruned subtrees.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
</country>
<region><li>Rhénanie-Palatinat</li>
</region>
<settlement><li>Trèves (Allemagne)</li>
</settlement>
<orgName><li>Université de Trèves</li>
</orgName>
</list>
<tree><country name="Allemagne"><noRegion><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
</noRegion>
<name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000867 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000867 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:12-0145043
   |texte=   An Exact Exponential Time Algorithm for POWER DOMINATING SET
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

An Exact Exponential Time Algorithm for POWER DOMINATING SET

An Exact Exponential Time Algorithm for POWER DOMINATING SET

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri